package algorithm_optimal_solution.TwoForkTree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

//非递归实现二叉树先序、中序、后序遍历：
// 先序使用栈。顶取右左入。头节点入栈，遍历栈不为空的时候，每次取出栈顶元素打印并判断右左子树是否为空需入栈。
// 中序使用栈。左全存顶取右单存。head不为空且栈不为空的时候，如果head左子树不为空则入栈并让head等于左子树，否则取出栈顶元素打印并让head等于栈顶元素右子树。
// 后序使用两个栈。两个栈与先序类似，但是顺序为顶取左右入。
// 后序使用一个栈。左全存左单取右单存右单取。head是上一次打印的节点，top为栈顶节点，头节点入栈，如果top左子树不为空且head不为左子树且不为右子树则左子树入栈（说明
//                      左子树没遍历完且未打印）。如果top右子树不为空且head不为右子树则右子树入栈（说明右子树没遍历完且未打印）。
//                      未满足以上条件则打印栈顶元素top（说明top的左右子树都已经打印，应打印top元素）
public class IteratorBeforeMidAfterTreeByNoRecursive {

    static class Node{
        private int value;
        private Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

    public void beforeTree(Node head,StringBuilder sb){
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()){
            head = stack.pop();
            sb.append(head.getValue()).append(" ");
            if(head.getRight() != null){
                stack.push(head.getRight());
            }
            if(head.getLeft() != null){
                stack.push(head.getLeft());
            }
        }
    }

    public void midTree(Node head,StringBuilder sb){
        Stack<Node> stack = new Stack<>();
        while(head != null || !stack.isEmpty()){
            if(head != null){
                stack.push(head);
                head = head.getLeft();
            }else{
                head = stack.pop();
                sb.append(head.getValue()).append(" ");
                head = head.getRight();
            }
        }
    }

    public void afterTree(Node head,StringBuilder sb){
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.push(head);
        while(!stack1.isEmpty()){
            head = stack1.pop();
            stack2.push(head);
            if(head.getLeft() != null){
                stack1.push(head.getLeft());
            }
            if(head.getRight() != null){
                stack1.push(head.getRight());
            }
        }
        while(!stack2.isEmpty()){
            sb.append(stack2.pop().getValue()).append(" ");
        }
    }

    public void afterTreeOneStack(Node head,StringBuilder sb){
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        Node top = null;
        while(!stack.isEmpty()){
            top = stack.peek();
            if(top.getLeft() != null && head != top.getLeft() && head != top.getRight()){
                stack.push(top.getLeft());
            }else if(top.getRight() != null && head != top.getRight()){
                stack.push(top.getRight());
            }else{
                sb.append(stack.pop().getValue()).append(" ");
                head = top;
            }
        }
    }

    public void createTree(Node head,int[][] arr){
        int left = arr[head.getValue()][0];
        int right = arr[head.getValue()][1];
        if(left != 0){
            Node leftNode = new Node(left);
            head.setLeft(leftNode);
            createTree(leftNode,arr);
        }
        if(right != 0){
            Node rightNode = new Node(right);
            head.setRight(rightNode);
            createTree(rightNode,arr);
        }
    }

    public static void main(String[] args)throws IOException {
        IteratorBeforeMidAfterTreeByNoRecursive main = new IteratorBeforeMidAfterTreeByNoRecursive();
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        String[] values = scanner.readLine().split(" ");
        int len = Integer.parseInt(values[0]);
        Node root = new Node(Integer.parseInt(values[1]));
        int[][] arr = new int[len + 1][2];
        String[] numbers = scanner.readLine().split(" ");
        arr[root.getValue()][0] = Integer.parseInt(numbers[1]);
        arr[root.getValue()][1] = Integer.parseInt(numbers[2]);
        for(int i = 1;i < len;i++){
            numbers = scanner.readLine().split(" ");
            int index = Integer.parseInt(numbers[0]);
            arr[index][0] = Integer.parseInt(numbers[1]);
            arr[index][1] = Integer.parseInt(numbers[2]);
        }
        StringBuilder sb = new StringBuilder();
        main.createTree(root,arr);
        main.beforeTree(root,sb);
        sb.append("\n");
        main.midTree(root,sb);
        sb.append("\n");
        main.afterTreeOneStack(root,sb);
        System.out.print(sb);
    }
}
